package algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序，是插入排序的一种，比插入排序多了一个增量gap
 * 一般 gap = n / 2;  gap = gap/2; 一直到gap = 1为止
 */
public class ShellSortTest {
    public static void main(String[] args) {
        int[] arr = {6,3,8,2,9,1,4,5};
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        int len = arr.length;
        boolean change = false;
        // 需要比较多少轮
        for(int gap = len/2; gap > 0; gap /= 2){
            // 从gap开始与前面的元素置换
            for(int i = gap; i < len; i++){
                change = false;
                // 确定了arr[i]之后，相当于i元素与之前每隔gap的有序的部分进行插入排序
                for(int j = i; j > 0; j -= gap){
                    if(j - gap >= 0 && arr[j] < arr[j - gap]){
                        int temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                        change = true;
                    }
                    if(!change){
                        break;
                    }
                }
            }
        }
    }
}
